﻿#include "pch.h"
#include "CppUnitTest.h"
#include "../ForTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;

namespace Graph3
{
	TEST_CLASS(LC3203)
	{
		//LC3203. 合并两棵树后的最小直径
		class Solution {
		public:
			int minimumDiameterAfterMerge(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
				const int D1 = D(edges1);
				const int D2 = D(edges2);
				return max(max(D1, D2), (D1 + 1) / 2 + (D2 + 1) / 2 + 1);
			}
			int D(vector<vector<int>>& edges) {
				auto neiBo = CNeiBo::Two(edges.size() + 1, edges, false);
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				int inx = max_element(leves.begin(), leves.end())- leves.begin();
				auto leves2 = CBFSLeve::Leve(neiBo, { inx });
				return *max_element(leves2.begin(), leves2.end());
			}
		};
	public:
		vector<vector<int>> edges1,edges2;
		TEST_METHOD(TestMethod11)
		{
			edges1 = { {0,1},{0,2},{0,3} }, edges2 = { {0,1} };
			auto res = Solution().minimumDiameterAfterMerge(edges1, edges2);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			edges1 = { {0,1},{0,2},{0,3},{2,4},{2,5},{3,6},{2,7} }, edges2 = { {0,1},{0,2},{0,3},{2,4},{2,5},{3,6},{2,7} }	;
			auto res = Solution().minimumDiameterAfterMerge(edges1, edges2);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod13)
		{
			edges1 = { {1,0},{2,3},{1,4},{2,1},{2,5} }
			, edges2 = { {4,5},{2,6},{3,2},{4,7},{3,4},{0,3},{1,0},{1,8} };
			auto res = Solution().minimumDiameterAfterMerge(edges1, edges2);
			AssertEx(6, res);
		}
	};

	TEST_CLASS(LCP8900)
	{
		//LCP8900 [USACO22DEC] Barn Tree S
		class Solution {
		public:
			vector<tuple<int,int,long long>> MinCommand(vector<int>& h,vector<vector<int>>& edge) {
				const int N = h.size();
				const long long sum = accumulate(h.begin(), h.end(), 0LL);
				const long long avg = sum / N;
				for (auto& v : edge) {
					v[0]--, v[1]--;
				}
				auto neiBo = CNeiBo::Two(N, edge, false);
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				auto leveNode = CBFSLeve::LeveNodes(leves);
				vector<int> par(N, -1);
				for (const auto& v : edge) {
					if (leves[v[0]] < leves[v[1]]) { par[v[1]] = v[0]; }
					else { par[ v[0]] = v[1]; }
				}
				vector<tuple<int, int, long long>> ans,ans2;
				vector<long long> nodeNeed(N);
				for (int i = leveNode.size() - 1; i >= 0; i--) {
					for (const auto& node : leveNode[i]) {
						nodeNeed[node] += avg - h[node];
						const int iP = par[node];
						if (-1 == iP) { continue; }
						nodeNeed[iP] += nodeNeed[node];
						if (nodeNeed[node] < 0) {
							ans.emplace_back(node+1, iP+1, -nodeNeed[node]);
						}
						else if(nodeNeed[node] > 0) {
							ans2.emplace_back( iP+1, node+1,nodeNeed[node]);
						}
					}					
				}
				ans.insert(ans.end(), ans2.rbegin(), ans2.rend());
				return ans;
			}			
		};		
		
	public:
		class CCheck
		{
		public:
			CCheck(vector<vector<int>>& edge, vector<int>& h) {
				m_sEdges.resize(h.size() + 1);
				for (const auto& v : edge) {
					m_sEdges[v[0]].emplace(v[1]);
					m_sEdges[v[1]].emplace(v[0]);
				}
				m_has = { 0 };
				m_has.insert(m_has.end(), h.begin(), h.end());
			}
			void Check(vector<tuple<int, int, long long>> ans) {
				for (const auto& [i, j, ll] : ans) {
					AssertEx(true, (bool)m_sEdges[i].count(j));
					Assert::IsTrue(ll > 0);
					Assert::IsTrue(m_has[i] >= ll);
					m_has[i] -= ll;
					m_has[j] += ll;
				}
				for (int i = 1; i + 1 < m_has.size(); i++) {
					AssertEx(m_has[i], m_has[i + 1]);
				}
			}
			vector<unordered_set<int>> m_sEdges;
			vector<long long> m_has;
		};
		vector<int> h;
		vector<vector<int>> edge;
		TEST_METHOD(TestMethod11)
		{			
			h = { 2,1,4,5 }, edge = { {1,2},{2,3},{2,4} };
			CCheck check(edge, h);
			auto res = Solution().MinCommand(h,edge);
			check.Check(res);
		}
		TEST_METHOD(TestMethod12)
		{
			h = { 0,0,0,0,5 }, edge = { {1, 2},{ 1,3 },{2,4},{3,5} };
			CCheck check(edge, h);
			auto res = Solution().MinCommand(h, edge);
			check.Check(res);
		}
		TEST_METHOD(TestMethod13)
		{
			h = { 0,0,0,0,(long long)1e9,(long long)1e9,(long long)1e9,(long long)1e9 }, 
				edge = { {1,2},{2,3},{3,4}, {4,5},{5,6},{6,7},{7,8} };
			CCheck check(edge, h);
			auto res = Solution().MinCommand(h, edge);
			check.Check(res);
		}
	};

	TEST_CLASS(P7165)
	{
		//P7165 [COCI2020-2021#1] Papričice
		class Solution {
		public:
			int Ans(vector<pair<int, int>>& edge) {
				const int N = edge.size() + 1;
				int ans = INT_MAX / 2;
				auto Ans = [&](int a, int b, int c) {
					const int iMax = max(max(a, b), c);
					const int iMin = min(min(a, b), c);
					ans = min(ans, iMax - iMin);
				};
				auto neiBo = CNeiBo::Two(N, edge, false, 1);
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				auto leveNodes = CBFSLeve::LeveNodes(leves);
				auto leveSorts = CBFSLeve::LeveSort(leves);
				vector<int> vs2(leveSorts.rbegin(), leveSorts.rend());
				vector<vector<int>> childs(N);
				for (int i = 0; i < N; i++) {
					for (const auto& next : neiBo[i]) {
						if (leves[next] < leves[i]) { continue; }
						childs[i].emplace_back(next);
					}
				}
				vector<int> cnt(N, 1);
				for (const auto& cur : vs2) {
					for (const auto& chi : childs[cur]) {
						cnt[cur] += cnt[chi];
					}
				}
				for (auto& v : childs) {
					for (int i = 1; i < v.size(); i++) {
						if (cnt[v[i]] > cnt[v[0]]) { swap(v[i], v[0]); }
					}
				}
				vector<set<int>> cc(N);
				auto Do33 = [&N, Ans](set<int>& tmp, int ccnt) {
					const int x = (N - ccnt) / 2;
					auto it = tmp.upper_bound(x);
					if (tmp.end() != it) {
						Ans(ccnt, *it, N - ccnt - *it);
					}
					if (tmp.begin() != it) {
						Ans(ccnt, *prev(it), N - ccnt - *prev(it));
					}
				};
				auto Do = [&](int cur) {
					cc[cur].swap(cc[childs[cur][0]]);
					for (int i = 1; i < childs[cur].size(); i++) {
						const auto& chi = childs[cur][i];
						cc[cur].insert(cc[chi].begin(), cc[chi].end());
					}
					auto it = cc[cur].upper_bound(cnt[cur] / 2);
					if (cc[cur].end() != it) {
						Ans(cnt[cur] - *it, *it, N - cnt[cur]);
					}
					if (cc[cur].begin() != it) {
						Ans(cnt[cur] - *prev(it), *prev(it), N - cnt[cur]);
					}
				};
				vector<vector<int>> tv(leveNodes.rbegin(), leveNodes.rend());
				for (auto& v : tv )
				{
					for (int i = 1; i < v.size(); i++) {
						if (cnt[v[i]] > cnt[v[0]]) { swap(v[0], v[i]); }
					}
					for (const auto& cur : v) {
						if (!childs[cur].empty()) { Do(cur); }
						cc[cur].emplace(cnt[cur]);
					}
					set<int> tmp1;
					for (int i = 1; i < v.size(); i++) {
						Do33(cc[v[0]], cnt[v[i]]);
						Do33(tmp1, cnt[v[i]]);
						tmp1.insert(cc[v[i]].begin(), cc[v[i]].end());
					}
					set<int> tmp2;
					for (int i = v.size() - 1; i > 0; i--) {
						tmp2.insert(cc[v[i]].begin(), cc[v[i]].end());
						Do33(tmp2, cnt[v[i - 1]]);
					}
				}
				return ans;
			}
		};
	public:
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod1)
		{
			edge = { {1,2},{1,3} };
			auto res = Solution().Ans(edge);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod11)
		{			
			edge = { {1,2},{2,3},{3,4} };
			auto res = Solution().Ans(edge);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			edge = { {1,2},{1,3},{3,4},{3,5},{5,6} };
			auto res = Solution().Ans(edge);
			AssertEx(0, res);
		}	
		TEST_METHOD(TestMethod13)
		{
			edge = { {1,3},{2,3},{3,4},{3,5},{5,6},{5,7},{7,8},{7,9} };
			auto res = Solution().Ans(edge);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod14)
		{
			edge = { {1,2},{1,3},{3,4} };
			auto res = Solution().Ans(edge);
			AssertEx(1, res);
		}
	};

	

	TEST_CLASS(P5603)
	{
		//P5603 小 C 与桌游 题解
		class CTopSort1
		{
		public:
			template < class T = vector<int> >
			void Init(const vector<T>& vNeiBo, bool bDirect)
			{
				const int iDelOutDeg = bDirect ? 0 : 1;
				m_c = vNeiBo.size();
				m_vBackNeiBo.resize(m_c);
				vector<int> vOutDeg(m_c);
				for (int cur = 0; cur < m_c; cur++)
				{
					vOutDeg[cur] = vNeiBo[cur].size();
					for (const auto& next : vNeiBo[cur])
					{
						m_vBackNeiBo[next].emplace_back(cur);
					}
				}
				vector<bool> m_vHasDo(m_c);
				priority_queue<int, vector<int>, greater<int>> que;
				for (int i = 0; i < m_c; i++)
				{
					if (vOutDeg[i] <= iDelOutDeg)
					{
						m_vHasDo[i] = true;
						que.emplace(i);
					}
				}
				while (que.size())
				{
					const int cur = que.top();
					que.pop();
					OnDo(cur);
					for (const auto& next : m_vBackNeiBo[cur])
					{
						if (m_vHasDo[next])
						{
							continue;
						}
						vOutDeg[next]--;
						if (vOutDeg[next] <= iDelOutDeg)
						{
							m_vHasDo[next] = true;
							que.emplace(next);
						}
					}
				};
			}
			int m_c;
		protected:
			virtual bool OnDo(int cur) = 0;
			vector<vector<int>> m_vBackNeiBo;
		};
		class CTopSortEx1 :public CTopSort1
		{
		public:
			virtual bool OnDo(int cur) override
			{
				m_ans += cur > m_pre;
				m_pre = max(cur,m_pre);
				return true;
			}
			int m_ans = 0, m_pre = -1;
		};

		class CTopSort2
		{
		public:
			template <class C = priority_queue<int, vector<int>, greater<int>>, class T = vector<int> >
			void Init(const vector<T>& vNeiBo, bool bDirect)
			{
				const int iDelOutDeg = bDirect ? 0 : 1;
				m_c = vNeiBo.size();
				m_vBackNeiBo.resize(m_c);
				vector<int> vOutDeg(m_c);
				for (int cur = 0; cur < m_c; cur++)
				{
					vOutDeg[cur] = vNeiBo[cur].size();
					for (const auto& next : vNeiBo[cur])
					{
						m_vBackNeiBo[next].emplace_back(cur);
					}
				}
				vector<bool> m_vHasDo(m_c);
				set<int> que;
				for (int i = 0; i < m_c; i++)
				{
					if (vOutDeg[i] <= iDelOutDeg)
					{
						m_vHasDo[i] = true;
						que.emplace(i);
					}
				}
				while (que.size())
				{
					int cur = *que.begin();
					if (cur > m_iMax) {
						cur = *que.rbegin();
					}
					que.erase(cur);
					OnDo(cur);
					for (const auto& next : m_vBackNeiBo[cur])
					{
						if (m_vHasDo[next])
						{
							continue;
						}
						vOutDeg[next]--;
						if (vOutDeg[next] <= iDelOutDeg)
						{
							m_vHasDo[next] = true;
							que.emplace(next);
						}
					}
				};
			}
			int m_c;
		protected:
			virtual bool OnDo(int cur) = 0;
			vector<vector<int>> m_vBackNeiBo;
			int m_iMax = -1;
		};
		class CTopSortEx2 :public CTopSort2
		{
		public:
			virtual bool OnDo(int cur) override
			{
				m_ans += cur > m_iMax;
				m_iMax = max(cur, m_iMax);
				return true;
			}
			int m_ans = 0;
		};
		class Solution {
		public:
			pair<int,int> Ans(const int N,vector<pair<int, int>>& edge) {				
				vector<vector<int>> neiBo(N);
				for (const auto& [from, to] : edge) {
					neiBo[to - 1].emplace_back(from - 1);
				}
				for (auto& v : neiBo) {
					sort(v.begin(), v.end());
					v.erase(unique(v.begin(), v.end()), v.end());
				}
				CTopSortEx1 ts;
				ts.Init(neiBo, true);
				CTopSortEx2 ts2;
				ts2.Init(neiBo, true);				
				return{ ts.m_ans,ts2.m_ans };
			}
		};
	public:
		int N;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod1)
		{
			edge = { {1,2},{1,3} };
			auto res = Solution().Ans(3, edge);
			AssertEx({ 3,2 }, res);
		}
		TEST_METHOD(TestMethod2)
		{
			edge = { {1,4},{2,1},{2,3} };
			auto res = Solution().Ans(4, edge);
			AssertEx({ 3,2 }, res);
		}
		TEST_METHOD(TestMethod3)
		{
			edge = { {1,2},{1,3},{2,6},{3,5},{5,4} };
			auto res = Solution().Ans(6, edge);
			AssertEx({ 5,3 }, res);
		}
	};

	TEST_CLASS(P3258)
	{
		//P3258 [JLOI2014] 松鼠的新家
		class Solution {
		public:
			vector<int> Ans(vector<int>&a, vector<pair<int, int>>& edge) {
				const int N = a.size();
				for (auto& i : a) {
					i--;
				}
				auto neiBo = CNeiBo::Two(N, edge, false, 1);
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				vector<int> pars(N, -1);
				for (int i = 0; i < N; i++) {
					for (const auto& j : neiBo[i]) {
						if (leves[j] < leves[i]) { continue; }
						pars[j] = i;
					}
				}
				C2Parents par2s(pars, leves);
				vector<int> diff(N);
				for (int i = 1; i < N; i++) {
					auto c = par2s.GetPublicParent(a[i - 1], a[i]);
					diff[a[i - 1]]++; diff[c]--;
					if (0 != a[i])
					{
						diff[pars[a[i]]]++;
						if (0 != c) {
							diff[pars[c]]--;
						}
					}
				}
				auto tmp = CBFSLeve::LeveSort(leves);
				vector<int> ans(N);
				vector<int> nodes(tmp.rbegin(), tmp.rend());
				for (const auto& cur : nodes) {
					ans[cur] = diff[cur];
					if (0 != cur) {
						diff[pars[cur]] += diff[cur];
					}
				}
				return ans;
			}
		};
	public:
		vector<int> a;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod1)
		{
			edge = { {1,2} };
			auto res = Solution().Ans(vector<int>{ 1,2 }, edge);
			AssertV(vector<int>{ 1,0 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			a = { 1,4,5,3,2 },edge = { {1,2},{2,4},{2,3},{4,5} };
			auto res = Solution().Ans(a, edge);
			AssertV(vector<int>{ 1,2,1,2,1 }, res);
		}
	};

	TEST_CLASS(P3663)
	{
		//【图论 BFS染色 并集查找 】P3663 [USACO17FEB] Why Did the Cow Cross the Road III S|普及+
		class Solution {
		public:
			int Ans(const int N ,vector<tuple<int,int,int,int>>& broad, vector<pair<int, int>>& pos) {
				auto Mask = [&](int r, int c) {return N * r + c; };
				vector<vector<int>> not1(N * N), neiBo(N * N);
				for (const auto& [r, c, r1, c1] : broad) {
					const int m1 = Mask(r - 1, c - 1);
					const int m2 = Mask(r1 - 1, c1 - 1);
					not1[m1].emplace_back(m2 );
					not1[m2].emplace_back(m1 );
				}
				auto Add = [&](int m1, int r,int c) {
					const int m2 = Mask(r, c);
					for (const auto& i : not1[m1]) {
						if (m2 == i) { return; }						
					}
					neiBo[m1].emplace_back(m2);
					neiBo[m2].emplace_back(m1);
				};
				for (int r = 0; r < N; r++) {
					for (int c = 0; c < N; c++) {
						const int m1 = Mask(r, c );
						if (r + 1 < N) { Add(m1, r + 1, c); }
						if(c+1 < N ) { Add(m1, r, c + 1); }
					}
				}
				CUnionFind uf(neiBo);
				vector<int> cnt(N * N);
				for (const auto&[r,c]:pos) {
					cnt[uf.GetConnectRegionIndex(Mask(r - 1, c - 1))]++;
				}
				int ans = 0;
				for (int i = 0; i < N * N; i++) {
					ans += cnt[i] * (pos.size() - cnt[i]);
				}
				return ans/2;
			}
		};
	public:
		int N;
		vector<tuple<int, int, int, int>> broad;
		vector<pair<int, int>> pos;
		TEST_METHOD(TestMethod1)
		{
			N = 3, broad = { {2,2,2,3},{3,3,3,2},{3,3,2,3} }, pos = { {3,3},{2,2},{2,3} };
			auto res = Solution().Ans(N, broad, pos);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			
		}
	};

	TEST_CLASS(P3671)
	{
		//【图论 并集查找】P3671 [USACO17OPEN] Where‘s Bessie? S|普及+
		class Solution {
		public:
			int Ans(const vector<vector<char>>& mat) {
				const int N = mat.size();				
				vector<tuple<int, int, int, int>> rects;
				auto Do = [&](const int r, const int c, const int r1) {		
					auto Mask = [&](int r, int c) {return N*r+c; };	
					int cc = -1;
					CUnionFind uf(N*N);
					for (int c1 = c; c1 < N; c1++) {						
						for (int r2 = r ;r2 <= r1;r2++)
						{	
							if ((c1 > c) && (mat[r2][c1] == mat[r2][c1 - 1])) {
								uf.Union(Mask(r2,c1), Mask(r2,c1-1));
							}
							if ((r2 > r) && (mat[r2][c1] == mat[r2 - 1][c1])) {
								uf.Union(Mask(r2, c1), Mask(r2 - 1, c1 ));
							}							
						}
						vector<pair<int, int>> colors;
						auto AddColor = [&](int iColor) {
							for (auto& pr : colors) {
								if (iColor == pr.first) { pr.second++; return; }
							}
							colors.emplace_back(iColor, 1);
						};
						vector<bool> regs(N * N);
						for (int c2 = c; c2 <= c1; c2++) {
							for (int r2 = r; r2 <= r1; r2++)
							{
								regs[uf.GetConnectRegionIndex(Mask(r2, c2))] = true;
							}
						}
						for (int i = 0; i < N * N; i++) {
							if (regs[i]) { AddColor(mat[i/N][i%N]); }
						}						
						if (2 !=colors.size()) { continue; }
						const int iMin = min(colors[0].second, colors[1].second);
						const int iMax = max(colors[0].second, colors[1].second);
						if ((1 == iMin) && (iMax > 1)) { cc = c1; }
					}
					if (-1 == cc) { return; }
					rects.emplace_back(r, c, r1, cc);
				};
				for (int r = 0; r < N; r++)
				{
					for (int c = 0; c < N; c++) {
						for (int r1 = r; r1 < N; r1++) {
							Do(r, c, r1);
						}
					}
				}
				int ans = 0;
				for (const auto& [r1, c1, r2, c2] : rects) {
					int cnt = 0;
					for (const auto& [r3, c3, r4, c4] : rects) {
						cnt += ((r3<=r1)&&(c3<=c1)&&(r2 <= r4)&&(c2<=c4));
					}
					ans += (cnt == 1);
				}
				return ans;
			}
		};
	public:
		vector<vector<char>> mat;
		TEST_METHOD(TestMethod1)
		{
			mat = { {'A','B','B','C'},{'B','B','B','C'},{'A','A','B','B'},{'A','B','B','C'} };
			auto res = Solution().Ans(mat);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{

		}
	};

	TEST_CLASS(P7299)
	{
		//【并集查找】P7299 [USACO21JAN] Dance Mooves S|普及+
		class Solution {
		public:
			vector<int> Ans(int N, const vector<pair<int,int>>& ab) {
				vector<int> pos(N);
				iota(pos.begin(), pos.end(), 0);
				vector<unordered_set<int>> vVis(N);
				for (int i = 0; i < N; i++) {
					vVis[i].emplace(i);
				}
				for ( auto [a, b] : ab) {
					a--; b--;
					swap(pos[a ], pos[b]);
					vVis[pos[a]].emplace(a);
					vVis[pos[b]].emplace(b);
				}
				CUnionFind uf(N);
				for (int i = 0; i < N; i++) {
					uf.Union(pos[i], i);
				}
				vector<int> ans(N);
				for ( const auto& [tmp,v] : uf.GetNodeOfRegion()) {
					unordered_set<int> s;
					for (const auto& cur : v) {
						for (const auto& vis : vVis[cur]) {
							s.emplace(vis);
						}
					}
					for (const auto& cur : v) {
						ans[cur] = s.size();
					}
				}
				return ans;
			}
		};
	public:
		int N;
		vector<pair<int, int>> ab;
		TEST_METHOD(TestMethod1)
		{
			N = 5,ab = { {1,3},{1,2},{2,3},{2,4} };
			auto res = Solution().Ans(N, ab);
			AssertV({ 4,4,3,4,1 }, res);
		}
	};

	TEST_CLASS(P8186)
	{
		//【图论 有向图 环 传递封包】P8186 [USACO22FEB] Redistributing Gifts S|普及+
		class Solution {
		public:
			vector<int> Ans(int N, vector<vector<int>>& mat) {
				vector<vector<int>> mat1(N, vector<int>(N,1));//临接矩阵，有边0，没有变1。
				for (int i = 0; i < N; i++) {
					for (const auto& j : mat[i]) {
						if (j == i + 1) { break; }
						mat1[i][j - 1] = 0;
					}
				}
				CFloyd<> floyd(N);
				floyd.m_vMat = mat1;
				auto dis = floyd.Dis();
				vector<int> ans(N);
				iota(ans.begin(), ans.end(), 1);
				for (int i = 0; i < N; i++) {
					for (auto j : mat[i]) {
						j--;
						if (i == j) { break; }
						if ((0 == mat1[i][j]) && (0 == dis[j][i])) {
							ans[i] = j + 1;
							break;
						}
					}
				}
				return ans;
			}
		};
	public:
		int N;
		vector<vector<int>> mat;
		TEST_METHOD(TestMethod1)
		{
			N = 4,mat = { {1,2,3,4},{1,3,2,4},{1,2,3,4},{1,2,3,4} };
			auto res = Solution().Ans(N, mat);
			AssertV({ 1,3,2,4 }, res);
		}
	};

	TEST_CLASS(P9267)
	{
			
		typedef CFrac<bigint > MYFRA;
		class Solution {
		public:
			string Ans(int N, vector<vector<int>>& child) {
				for (auto& v : child) {
					for (auto& i : v) {
						i--;
					}
				}				
				vector< MYFRA> cnt(N, MYFRA(0));
				cnt[0] = MYFRA(1);
				for (int i = 0; i < N; i++) {
					if (0 == child[i].size()) { continue; }
					auto send = cnt[i] / MYFRA(child[i].size());
					for (const auto& chi : child[i]) {
						cnt[chi] = cnt[chi] + send;
					}
				}
				bigint ans = 1;
				for (int i = 0; i < N; i++) {
					ans = lcm(ans, cnt[i].m_i2);
				}
				return ans.to_string();
			}
		};
	public:
		int N;
		vector<vector<int>> vchi;
		TEST_METHOD(TestMethod1)
		{
			N = 7, vchi = { {2,3,5},{3,6},{5,6,7},{6},{7},{},{} };
			auto res = Solution().Ans(N, vchi);
			AssertEx(string("6"), res);
		}
		TEST_METHOD(TestMethod2)
		{
			N = 3, vchi = { {},{1,3},{} };
			auto res = Solution().Ans(N, vchi);
			AssertEx(string("1"), res);
		}
	};
}


